;;;
;;; Calculate the sum of all the primes below two million.
;;; takes 60+ senconds to get the answer, 142913828922

;;; Very slow if n is large (like 2 million) ...
(defun primep-1 (n)
  (defun test-inner (seeds result)
	(cond ((equal result t) nil)
		  ((null seeds) t)
	      (t (test-inner (cdr seeds) (= (mod n (car seeds)) 0)))))
  (if (<= n 1)
	  nil
      (test-inner (range 2 (sqrt n)) nil)))

;;; duplicated in p7.lisp
(defun primep-2 (n)
  (cond ((= n 1) nil)
		((< n 4) t)
		((zerop (mod n 2)) nil)
		((< n 9) t) ;;; already excluded 4,6,8
		((zerop (mod n 3)) nil)
		(t (do ((r (floor (sqrt n))) (f 5 (+ f 6)))
			   ((or (zerop (mod n f)) (zerop (mod n (+ f 2))) (> f r))
				(if (> f r)
				     t
					 nil))
			   ;(print f)
			   ))))

;;;TODO defun can-divided (n x)

(defun range (start end &optional (step 1))
  (loop for i from start to end by step collect i)) 

(defun prime-list (start end &optional (prime-test 'primep-1))
  (remove-if-not
	prime-test
	(remove-if
	  (lambda (x)
		(or (= (mod x 2) 0) (= (mod x 3) 0) (= (mod x 5) 0)))
	  (range start end 2))))

(defun euler10-failed ()
  (apply
	'+
	(append '(2 3 5) (prime-list 7 2000000 'primep-2))))

(defun euler10 ()
  (loop for i from 7 to 2000000 by 2
		and result = 10 then (if (primep-2 i) (+ result i) result)
		finally (return result)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;(format t "~a~%" (time (primep-2 71)))
(defparameter *upper-limit* 20000)
(format t "~a~%" (length (prime-list 1 1000)))
;(format t "~a~%" (time (prime-list 7 *upper-limit* 'primep-2)))
;(format t "~a~%" (equal (prime-list 7 *upper-limit*)(prime-list 7 *upper-limit* 'primep-2)))

;;; takes arount 60seconds 
;;; TODO apply the more effcient algorithm in the its document
;(format t "~a~%" (time (euler10)))
